package com.study.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/submissions/
public class Solution_438 {
    public List<Integer> findAnagrams(String s, String p) {
        int m = s.length();
        int n = p.length();
        List<Integer> res = new ArrayList<>();
        if(m < n){
            return res;
        }
        int[] cnt_p = new int[26];
        int[] cnt_s = new int[26];
        for(int i=0;i<n;i++) {
            cnt_p[p.charAt(i)-'a']++;
            cnt_s[s.charAt(i)-'a']++;
        }
        if(Arrays.equals(cnt_s, cnt_p)) {
            res.add(0);
        }

        for(int i=n;i<m;i++) {
            cnt_s[s.charAt(i)-'a']++;
            cnt_s[s.charAt(i-n)-'a']--;
            if(Arrays.equals(cnt_s, cnt_p)) {
                res.add(i-n+1);
            }
        }
        return res;
    }
}
